class Solution {
public:
    long long validSubstringCount(string s, string t) {
        // 本题类似 76.最小覆盖子串
        if(s.size() < t.size()) 
            return 0;
        int hash1[26] = { 0 }, hash2[26] = { 0 };
        for(char &ch : t)
            hash2[ch - 'a']++;
        int n = s.size(), left = 0;
        long long ans = 0;
        auto cmp = [&](int hash1[26], int hash2[26])->bool
        {
            for(int i = 0; i < 26; i++)
                if(hash1[i] < hash2[i])
                    return false;
            return true;
        };
        // 时间复杂度是 O(26 * n)
        for(int i = 0; i < n; i++)
        {
            // 入窗口
            hash1[s[i] - 'a']++;

            // 找到使窗口最小且满足窗口内字符的出现个数都 >= hash2
            // 如果while循环结束，那么left的位置是刚刚好不满足窗口内字符的出现个数都 >= hash2
            // 所以left - 1是刚好满足，因此 0, 1, 2, ..., left - 1, 都是包含字符串t中所有字符的
            while(cmp(hash1, hash2))
                hash1[s[left++] - 'a']--;
            ans += left;    // 0 到 left - 1，那么一共是 left 个
        }
        return ans;
    }
};